package com.copa.l234;

/**
 * @author copa
 * @createDate 2022-05-31 09:10
 * @function 递归+双指针
 */
public class Test3 {

    // 定义一个全局变量p，方便等会进行比较
    private ListNode p = new ListNode();

    public boolean isPalindrome(ListNode head) {
        // 先把p指向head
        p = head;
        // 递归
        return recursion(head);
    }

    private boolean recursion(ListNode head) {
        if (head == null) {
            // 若遍历到head已经没有值了，则直接返回
            return true;
        }
        if (!recursion(head.next)) {
            // 若还没有遍历完head或者是比对时值不一致
            return false;
        }
        if (p.val != head.val) {
            // 若比对时值不一致
            return false;
        }
        // 这次比对完成，则把p往下移，然后跟递归回来的head进行比对
        p = p.next;
        // 若比对数据一致，则返回true
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);
//        head.next.next.next.next = new ListNode(1);
        System.out.println(new Test3().isPalindrome(head));
    }
}
